package com.itzmn.datastructure.newcode;

import java.util.HashMap;
import java.util.List;
import java.util.Stack;

/**
 * @Author: 张梦楠
 * @Date: 2019/1/2 16:09
 * 简书：https://www.jianshu.com/u/d611be10d1a6
 * 码云：https://gitee.com/zhangqiye
 * @Description: 并查集，简单实现
 *
 *  使用hash表实现
 *  并查集在初始化的时候需要将数据传入，固定不变
 *  1.初始化
 *  2.找元素的代表节点，
 *  3.合并两个节点
 *  4.判断两个节点是否是同一个集合（代表节点是否相同）
 *  在处理的时候，需要将链表扁平化
 */
public class UnionFind {

    public class UnionFindNode{

    }
    // 用来存储节点，和父亲节点。key是当前节点，value是父亲节点
    private HashMap<UnionFindNode,UnionFindNode> fatherMap;
    // 用来存储当前节点所在的集合的size大小
    private HashMap<UnionFindNode,Integer> sizeMap;
    private int size;


    public UnionFind(List<UnionFindNode> nodes){
        init(nodes);
    }

    // 初始化方法
    private void init(List<UnionFindNode> nodes) {
        size = 0;
        fatherMap = new HashMap<>();
        sizeMap = new HashMap<>();

        for (int i=0; i<nodes.size(); i++){
            // 每一个节点的的父亲都是自己，说明每个节点都是一个集合
            fatherMap.put(nodes.get(i),nodes.get(i));
            // 每一个节点所在的集合的节点个数都是1
            sizeMap.put(nodes.get(i),1);
        }

    }

    /**
     * 查找这个节点所在集合的代表节点，在查找过程中，将上层节点的父亲设置为代表节点
     * @param node
     * @return
     */
    private UnionFindNode findHead(UnionFindNode node){

        Stack<UnionFindNode> stack = new Stack<>();

        UnionFindNode cur = node;

        UnionFindNode parent = fatherMap.get(cur);
        // 直到找到当前节点和父亲是一样的
        while (cur != parent){
            stack.push(cur);
            cur = parent;
            parent = fatherMap.get(cur);
        }
        // 找到父亲，也就是代表节点

        // 将路径中的所有节点的父亲都设置为代表节点
        while (!stack.isEmpty()){
            UnionFindNode pop = stack.pop();
            fatherMap.put(pop,parent);
        }
        return parent;
    }


    /**
     * 判断两个数据，是否是在同一个集合，只需要判断两个节点所在集合的代表节点是否相同
     * @param A
     * @param B
     * @return
     */
    public boolean isSameSet(UnionFindNode A,UnionFindNode B){
        return findHead(A) == findHead(B);
    }

    /**
     * 合并两个节点所在集合
     * @param A
     * @param B
     */
    public void union(UnionFindNode A,UnionFindNode B){

        UnionFindNode head = findHead(A);
        UnionFindNode head1 = findHead(B);
        // 如果在同一个集合，就不再合并
        if (head == head1){
            return;
        }

        Integer aSize = sizeMap.get(head);
        Integer bSize = sizeMap.get(head1);

        // 将短的加在长的上面
        if (aSize >= bSize){
            fatherMap.put(head1,head);
            sizeMap.put(head,aSize+bSize);
        }else {
            fatherMap.put(head,head1);
            sizeMap.put(head1,aSize+bSize);
        }
    }


}
